Introduction

The goal of this document is to do some exploratory analysis on dynamic Gröbner Basis algorithms. Gröbner bases (GB) are a fundamental tool in computer algebra to solve multivariate polynomial (non-linear) systems, among other applications. Traditional static Gröbner Basis algorithms receive an ordering (a vector) as part of the input. The performance of the algorithm, as well as the size of the output itself strongly depends on this input ordering. Dynamic Gröbner Basis algorithms were proposed to avoid having to choose an ordering a priori, computing one during the execution of the algorithm itself, hoping that this would lead to at least some of the following:

These are the main values that are computed in the experiments that follow. Six algorithms were used:

Due to particular traits of these algorithms, the perturbation and random algorithms only look for new orderings every 10 iterations of the Gröbner basis computation. It would also be interesting to find a better period more rigorously, but we do not do that here.

Experimental setup and environment

All algorithms were implemented in the Sage computer algebra system (version 8.8, Python version 3.7.3) and share all basic functionality from the underlying algorithm used to compute Gröbner Bases. Our implementation is based on that of (Caboara and Perry 2014). Experiments were run on an AMD FX(tm)-8150 Eight-Core Processor @ 3.60GHz machine with 32GB of RAM.

All 30 instances were extracted from Christian Eder’s benchmark library for Gröbner Bases. Each algorithm was run on every instance 30 times, the presented results corresponding to the average of these runs.

Partial results from some previous works

The following table shows the results reported in (Caboara and Perry 2014). Timings are not reported in the paper. We cannot reproduce these results, even using the code supplied in the original paper.

## Warning: Column `instance` joining factors with different levels, coercing
## to character vector
##      instance Original polynomials Original monomials Our polynomials
## 1    cyclicn5                   11                 68              10
## 2    cyclicn6                   20                129              19
## 3    cyclicn7                   63               1049              59
## 4   cyclicnh5                   11                 98              21
## 5   cyclicnh6                   33                476              48
## 6   cyclicnh7                  222               5181             113
## 7   katsuran6                   22                 54              23
## 8   katsuran7                   49                104              43
## 9  katsuranh6                   23                164              24
## 10 katsuranh7                   46                352              52
##    Our monomials
## 1             89
## 2            360
## 3           6496
## 4            296
## 5           2580
## 6          29371
## 7            593
## 8           2156
## 9            634
## 10          2600

There are multiple possibilities for why we could not reproduce the results of the original paper. One is that their code may have changed between the publication of the paper and our access. As they did not provide the instances, only their names (they are all classical benchmarks in the literature) there may be slight differences in the instances themselves. An instance is a list of polynomials - they may have been provided in a different order, leading to different results. Also, one of the properties of the instances (characteristic) was not reported in the paper, so we had to choose an arbitrary value common in the literature.

For completeness, we also show the results from (Perry 2017), that uses a slightly modified version of the caboara-perry algorithm and a simple implementation in C++.

## Warning: Column `instance` joining factors with different levels, coercing
## to character vector
##    instance Their polynomials Their monomials Their time Our polynomials
## 1  cyclicn4                 7              29      0.008               5
## 2 cyclicnh4                 4              15      0.014               5
## 3  cyclicn5                13             165      0.059              10
## 4 cyclicnh5                11             148      0.025              21
## 5  cyclicn6                21             482      1.450              19
## 6 cyclicnh6                38            1340      0.386              48
## 7  cyclicn7                54            9156    243.000              59
## 8 cyclicnh7               107           27645     31.400             113
##   Our monomials     Our time
## 1            21    0.1133333
## 2            21    0.1711538
## 3            89    0.8042308
## 4           296    0.5724000
## 5           360   11.8400000
## 6          2580    2.9153846
## 7          6496 1634.3835714
## 8         29371   68.9342308

Our implementation is much slower, but that is expected, as the implementation from (Perry 2017) is in C++ and ours is in Sage / Python. It is interesting to note, however, that for most instances their implementation is faster by almost a factor of 10. This is not the case of cyclicnh7, where it is only about 2 times faster. This points to an algorithmic advantage of the caboara-perry algorithm in this case.

Exploratory analysis

Classical reduction vs F4

Two reducers (a component of the general Gröbner Basis algorithm) were implemented: classical (based on polynomial arithmetic) and F4 (introduced in (Faugère 1999), uses matrix row reduction). F4 is usually considered to be faster in the context of traditional static Gröbner Basis algorithms. We observe this as well in our implementation, as shown by the table below (geometric means over all instances of the Static algorithm).

## # A tibble: 2 x 2
##   reducer    time
##   <fct>     <dbl>
## 1 classical 0.408
## 2 F4        0.246

Is the speedup of using the F4 reducer kept for dynamic algorithms? In average, yes.

## [1] "Classical reducer running time (over all algorithms): "
## [1] 1.465916
## [1] "F4 reducer running time (over all algorithms):"
## [1] 0.8378402

The speedup of the F4 reducer is kept for most, but not all, pairs of instances and algorithms. The following graphs show results instance by instance, for three algorithms (Caboara-Perry, Static, Perturbation).

## Warning: Removed 2 rows containing missing values (geom_col).

## Warning: Removed 2 rows containing missing values (geom_col).

First, we want to visualize the running time of the algorithms per instance, comparatively, and to find the algorithm that runs the fastest for each instance.

## # A tibble: 10 x 9
## # Groups:   algorithm [5]
##    algorithm reducer  time overhead polynomials monomials degree
##    <fct>     <fct>   <dbl>    <dbl>       <dbl>     <dbl>  <dbl>
##  1 caboara-… classi… 2.10    1.00          21.0      481.   8.88
##  2 caboara-… F4      1.28    0.877         21.6      401.   8.74
##  3 perturba… classi… 0.617   0.252         21.9      384.   6.09
##  4 perturba… F4      0.431   0.116         25.1      479.   6.34
##  5 static    classi… 0.408 NaN             28.2      529.   6.70
##  6 static    F4      0.246 NaN             28.2      529.   6.70
##  7 random    classi… 1.73    0.325         23.3      418.   6.56
##  8 random    F4      0.483   0.0801        27.8      529.   6.89
##  9 localsea… classi… 9.68    9.16          15.8      299.   8.42
## 10 localsea… F4      8.90    8.27          18.6      282.   7.78
## # … with 2 more variables: sreductions <dbl>, timeout <int>
## Warning: Removed 15 rows containing missing values (geom_point).

## Warning: Removed 15 rows containing missing values (geom_point).

Now, we compare the sizes of the output bases, in number of polynomials.

## Warning: Removed 9 rows containing missing values (geom_col).

Here, the dynamic algorithms (perturbation and caboara-perry) get better results than static for larger instances, such as cyclicn6 and cyclicnh6. All algorithms tie or are close to tying for the katsura family. It can be shown that the affine Katsura instance with parameter \(n\) has a Gröbner Basis with \(n\) polynomials. All algorithms are far from this lower bound, which means the dynamic algorithms should be improved to deal with this kind of situation better.

We should also check what happens to the degrees.

## Warning: Removed 9 rows containing missing values (geom_col).

Algorithms tie in terms of degree for most Katsuras. For the cyclics, perturbation seems to perform well, specially for the larger ones.

Quick idea: can we show that getting smaller bases rises the degree? (the graphic below looks awful, but I think it shows that the answer is yes for some instances, no to others).

## Warning: Removed 9 rows containing missing values (geom_path).

Check correlation between number of S-reductions and time.

## Warning: Removed 9 rows containing missing values (geom_point).

There is clearly a positive correlation (graphically) and computing it we get NA.

We should also test:

  • polynomials and time: NA
  • monomials and time: NA
  • degree and time: NA

The first two are aroung \(0.5\), degree is \(0.81\). Graphing degree, we get:

## Warning: Removed 9 rows containing missing values (geom_point).

I should also measure fraction of time taken managing the queue, unrestricted vs restricted algorithms.

## Warning: Removed 9 rows containing missing values (geom_col).

#Generating some tables for the paper

## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrr}
##   \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\ 
##   \hline
## butcher8 & 15.93 & 2.15 &  34 & 911 &   5 & 368 \\ 
##   cyclicn4 & 0.11 & 0.10 &   5 &  21 &   5 &   8 \\ 
##   cyclicn5 & 0.80 & 0.48 &  10 &  89 &  15 &  87 \\ 
##   cyclicn6 & 11.84 & 3.78 &  19 & 360 &  48 & 406 \\ 
##   cyclicn7 & 1634.38 & 86.60 &  59 & 6496 & 203 & 2323 \\ 
##   cyclicnh4 & 0.17 & 0.15 &   5 &  21 &   5 &   8 \\ 
##   cyclicnh5 & 0.57 & 0.47 &  21 & 296 &  12 &  49 \\ 
##   cyclicnh6 & 2.92 & 1.44 &  48 & 2580 &  14 & 153 \\ 
##   cyclicnh7 & 68.93 & 28.48 & 113 & 29371 &  13 & 429 \\ 
##   econ4 & 0.12 & 0.10 &   5 &  24 &   3 &  11 \\ 
##   econ5 & 0.16 & 0.13 &   6 &  48 &   6 &  13 \\ 
##   econ6 & 0.59 & 0.44 &   8 & 122 &   9 &  49 \\ 
##   econ7 & 1.75 & 0.93 &  22 & 553 &   6 & 111 \\ 
##   econh4 & 0.13 & 0.11 &   5 &  21 &   4 &   6 \\ 
##   econh5 & 0.21 & 0.18 &   9 &  55 &   5 &  15 \\ 
##   econh6 & 1.93 & 1.21 &  35 & 534 &   8 & 130 \\ 
##   econh7 & 8.48 & 3.38 &  68 & 1985 &  15 & 324 \\ 
##   f633 & 1.86 & 1.04 &  31 & 914 &   8 & 148 \\ 
##   f633h & 72.66 & 10.23 &  57 & 14827 &  10 & 296 \\ 
##   fateman & 2.37 & 1.76 &  43 & 1882 &  20 & 110 \\ 
##   fatemanh & 0.80 & 0.63 &  22 & 925 &  12 &  47 \\ 
##   katsuran4 & 0.14 & 0.11 &   7 &  55 &   4 &  12 \\ 
##   katsuran5 & 0.47 & 0.39 &  12 & 193 &   6 &  32 \\ 
##   katsuran6 & 1.21 & 0.82 &  23 & 593 &   6 &  72 \\ 
##   katsuran7 & 4.01 & 1.29 &  43 & 2156 &   7 & 177 \\ 
##   katsuranh4 & 0.28 & 0.25 &   8 &  58 &   4 &  15 \\ 
##   katsuranh5 & 0.67 & 0.57 &  14 & 197 &   5 &  34 \\ 
##   katsuranh6 & 2.58 & 2.12 &  24 & 634 &   6 &  77 \\ 
##   katsuranh7 & 8.59 & 4.72 &  52 & 2600 &   7 & 231 \\ 
##   noon7 & 2727.26 & 29.95 & 398 & 264267 &  19 & 3256 \\ 
##    \hline
## \end{tabular}
## \caption{Experimental results for  caboara-perry  using Buchberger reducer} 
## \end{table}
## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrr}
##   \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\ 
##   \hline
## butcher8 & NA & NA & NA & NA & NA & NA \\ 
##   cyclicn4 & 0.05 & 0.03 &   7 &  30 &   6 &  29 \\ 
##   cyclicn5 & 1.01 & 0.81 &  12 & 114 &  15 & 571 \\ 
##   cyclicn6 & 7.58 & 2.36 &  21 & 415 &  48 & 4892 \\ 
##   cyclicn7 & 379.04 & 103.91 & 135 & 17053 &  37 & 50945 \\ 
##   cyclicnh4 & 0.11 & 0.09 &   7 &  29 &   8 &  38 \\ 
##   cyclicnh5 & 0.60 & 0.49 &  20 & 309 &  12 & 314 \\ 
##   cyclicnh6 & 8.47 & 7.49 &  43 & 2112 &  12 & 899 \\ 
##   cyclicnh7 & 146.30 & 111.59 & 160 & 38330 &  15 & 5999 \\ 
##   econ4 & 0.04 & 0.02 &   7 &  29 &   2 &  35 \\ 
##   econ5 & 0.21 & 0.18 &  11 &  80 &   3 & 152 \\ 
##   econ6 & 1.04 & 0.76 &   7 & 104 &  14 & 931 \\ 
##   econ7 & 2.13 & 1.15 &  22 & 617 &  10 & 2359 \\ 
##   econh4 & 0.11 & 0.09 &  10 &  44 &   6 &  56 \\ 
##   econh5 & 0.53 & 0.46 &  20 & 153 &  10 & 288 \\ 
##   econh6 & 1.47 & 1.33 &  29 & 381 &   7 & 384 \\ 
##   econh7 & 7.84 & 5.33 &  79 & 2179 &  18 & 3449 \\ 
##   f633 & 4.96 & 3.36 &  40 & 1215 &   7 & 3983 \\ 
##   f633h & 3.88 & 2.57 &  55 & 1498 &   9 & 3370 \\ 
##   fateman & 2.06 & 1.39 &  40 & 2056 &  17 & 680 \\ 
##   fatemanh & 1.31 & 1.09 &  22 & 1060 &  12 & 351 \\ 
##   katsuran4 & 0.06 & 0.04 &   7 &  49 &   4 &  44 \\ 
##   katsuran5 & 0.33 & 0.28 &  13 & 168 &   5 & 140 \\ 
##   katsuran6 & 1.12 & 0.94 &  21 & 518 &   6 & 375 \\ 
##   katsuran7 & 4.68 & 1.21 &  41 & 2268 &   8 & 2677 \\ 
##   katsuranh4 & 0.15 & 0.13 &   9 &  65 &   5 &  66 \\ 
##   katsuranh5 & 0.45 & 0.40 &  13 & 169 &   5 & 155 \\ 
##   katsuranh6 & 2.56 & 2.37 &  22 & 540 &   6 & 382 \\ 
##   katsuranh7 & 6.35 & 5.38 &  48 & 2272 &   7 & 1079 \\ 
##   noon7 & NA & NA & NA & NA & NA & NA \\ 
##    \hline
## \end{tabular}
## \caption{Experimental results for  caboara-perry  using F4 reducer} 
## \end{table}
## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrr}
##   \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\ 
##   \hline
## butcher8 & 15.33 & 2.27 &  44 & 1300 &   4 & 393 \\ 
##   cyclicn4 & 0.05 & 0.03 &   7 &  30 &   6 &  12 \\ 
##   cyclicn5 & 0.48 & 0.22 &  20 & 232 &   8 & 113 \\ 
##   cyclicn6 & 5.57 & 0.92 &  45 & 1135 &   9 & 354 \\ 
##   cyclicn7 & 511.23 & 20.61 & 209 & 27185 &  12 & 2099 \\ 
##   cyclicnh4 & 0.06 & 0.04 &   7 &  30 &   6 &  12 \\ 
##   cyclicnh5 & 0.30 & 0.20 &  12 & 171 &   7 &  38 \\ 
##   cyclicnh6 & 1.14 & 0.51 &  34 & 1540 &   9 & 102 \\ 
##   cyclicnh7 & 44.31 & 4.17 & 121 & 28595 &  12 & 467 \\ 
##   econ4 & 0.05 & 0.03 &   7 &  29 &   2 &  13 \\ 
##   econ5 & 0.14 & 0.10 &  11 &  82 &   3 &  28 \\ 
##   econ6 & 0.32 & 0.19 &  18 & 232 &   4 &  61 \\ 
##   econ7 & 1.08 & 0.24 &  32 & 747 &   4 & 153 \\ 
##   econh4 & 0.06 & 0.04 &   8 &  34 &   5 &  14 \\ 
##   econh5 & 0.17 & 0.13 &  15 & 104 &   7 &  37 \\ 
##   econh6 & 0.48 & 0.25 &  28 & 346 &   9 &  94 \\ 
##   econh7 & NA & NA & NA & NA & NA & NA \\ 
##   f633 & 1.18 & 0.39 &  47 & 1022 &   4 & 214 \\ 
##   f633h & 1.28 & 0.47 &  47 & 977 &   6 & 214 \\ 
##   fateman & 0.40 & 0.19 &  27 & 1009 &  14 &  63 \\ 
##   fatemanh & 0.47 & 0.26 &  27 & 1009 &  14 &  63 \\ 
##   katsuran4 & 0.07 & 0.05 &   7 &  49 &   4 &  12 \\ 
##   katsuran5 & 0.18 & 0.12 &  13 & 168 &   5 &  31 \\ 
##   katsuran6 & 0.52 & 0.23 &  22 & 528 &   6 &  70 \\ 
##   katsuran7 & 2.62 & 0.63 &  41 & 1923 &   7 & 169 \\ 
##   katsuranh4 & 0.07 & 0.06 &   7 &  49 &   4 &  12 \\ 
##   katsuranh5 & 0.21 & 0.15 &  13 & 168 &   5 &  31 \\ 
##   katsuranh6 & 0.57 & 0.28 &  22 & 528 &   6 &  70 \\ 
##   katsuranh7 & 2.63 & 0.72 &  41 & 1923 &   7 & 169 \\ 
##   noon7 & NA & NA & NA & NA & NA & NA \\ 
##    \hline
## \end{tabular}
## \caption{Experimental results for  perturbation  using Buchberger reducer} 
## \end{table}
## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrr}
##   \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\ 
##   \hline
## butcher8 & 3.28 & 0.27 &  54 & 1796 &   4 & 2481 \\ 
##   cyclicn4 & 0.01 & 0.00 &   7 &  30 &   6 &  43 \\ 
##   cyclicn5 & 0.33 & 0.12 &  20 & 232 &   8 & 600 \\ 
##   cyclicn6 & 1.61 & 0.17 &  45 & 1135 &   9 & 1710 \\ 
##   cyclicn7 & 72.06 & 2.14 & 209 & 27185 &  12 & 13791 \\ 
##   cyclicnh4 & 0.02 & 0.00 &   7 &  30 &   6 &  43 \\ 
##   cyclicnh5 & 0.13 & 0.07 &  12 & 171 &   7 & 140 \\ 
##   cyclicnh6 & 0.41 & 0.08 &  34 & 1540 &   9 & 515 \\ 
##   cyclicnh7 & 18.35 & 0.53 & 121 & 28595 &  12 & 3705 \\ 
##   econ4 & 0.05 & 0.04 &   7 &  29 &   2 &  35 \\ 
##   econ5 & 0.09 & 0.05 &  11 &  82 &   3 & 162 \\ 
##   econ6 & 0.20 & 0.10 &  18 & 232 &   4 & 417 \\ 
##   econ7 & 0.52 & 0.08 &  32 & 747 &   4 & 1133 \\ 
##   econh4 & 0.06 & 0.05 &   8 &  34 &   5 &  31 \\ 
##   econh5 & 0.10 & 0.07 &  15 &  98 &   6 & 123 \\ 
##   econh6 & 0.23 & 0.09 &  28 & 346 &   9 & 617 \\ 
##   econh7 & 0.66 & 0.11 &  51 & 1127 &  10 & 1485 \\ 
##   f633 & 0.88 & 0.13 &  47 & 1022 &   4 & 2278 \\ 
##   f633h & 0.87 & 0.15 &  47 & 977 &   6 & 2025 \\ 
##   fateman & 0.33 & 0.10 &  27 & 1009 &  14 & 471 \\ 
##   fatemanh & 0.35 & 0.13 &  27 & 1009 &  14 & 471 \\ 
##   katsuran4 & 0.07 & 0.05 &   7 &  49 &   4 &  44 \\ 
##   katsuran5 & 0.13 & 0.07 &  13 & 168 &   5 & 219 \\ 
##   katsuran6 & 0.29 & 0.08 &  22 & 528 &   6 & 537 \\ 
##   katsuran7 & 1.34 & 0.09 &  41 & 1923 &   7 & 1346 \\ 
##   katsuranh4 & 0.08 & 0.06 &   7 &  49 &   4 &  44 \\ 
##   katsuranh5 & 0.14 & 0.07 &  13 & 168 &   5 & 219 \\ 
##   katsuranh6 & 0.33 & 0.09 &  22 & 528 &   6 & 537 \\ 
##   katsuranh7 & 1.31 & 0.12 &  41 & 1923 &   7 & 1346 \\ 
##   noon7 & 474.42 & 1.07 & 493 & 76254 &  14 & 111944 \\ 
##    \hline
## \end{tabular}
## \caption{Experimental results for  perturbation  using F4 reducer} 
## \end{table}
## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrr}
##   \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\ 
##   \hline
## butcher8 & 13.92 & 0.00 &  54 & 1796 &   4 & 420 \\ 
##   cyclicn4 & 0.01 & 0.00 &   7 &  30 &   6 &  12 \\ 
##   cyclicn5 & 0.24 & 0.00 &  20 & 232 &   8 & 113 \\ 
##   cyclicn6 & 4.44 & 0.00 &  45 & 1135 &   9 & 354 \\ 
##   cyclicn7 & 484.02 & 0.00 & 209 & 27185 &  12 & 2099 \\ 
##   cyclicnh4 & 0.01 & 0.00 &   7 &  30 &   6 &  12 \\ 
##   cyclicnh5 & 0.25 & 0.00 &  38 & 538 &  13 & 113 \\ 
##   cyclicnh6 & 4.91 & 0.00 &  99 & 3502 &  15 & 389 \\ 
##   cyclicnh7 & 488.70 & 0.00 & 443 & 79897 &  19 & 2199 \\ 
##   econ4 & 0.01 & 0.00 &   7 &  29 &   2 &  13 \\ 
##   econ5 & 0.03 & 0.00 &  11 &  82 &   3 &  28 \\ 
##   econ6 & 0.12 & 0.00 &  18 & 232 &   4 &  61 \\ 
##   econ7 & 0.79 & 0.00 &  32 & 747 &   4 & 153 \\ 
##   econh4 & 0.01 & 0.00 &   8 &  34 &   5 &  14 \\ 
##   econh5 & 0.04 & 0.00 &  15 & 104 &   7 &  37 \\ 
##   econh6 & 0.20 & 0.00 &  28 & 346 &   9 &  94 \\ 
##   econh7 & 1.23 & 0.00 &  51 & 1127 &  10 & 213 \\ 
##   f633 & 0.74 & 0.00 &  47 & 1022 &   4 & 214 \\ 
##   f633h & 0.75 & 0.00 &  47 & 977 &   6 & 214 \\ 
##   fateman & 0.21 & 0.00 &  27 & 1009 &  14 &  63 \\ 
##   fatemanh & 0.20 & 0.00 &  27 & 1009 &  14 &  63 \\ 
##   katsuran4 & 0.02 & 0.00 &   7 &  49 &   4 &  12 \\ 
##   katsuran5 & 0.05 & 0.00 &  13 & 168 &   5 &  31 \\ 
##   katsuran6 & 0.27 & 0.00 &  22 & 528 &   6 &  70 \\ 
##   katsuran7 & 1.91 & 0.00 &  41 & 1923 &   7 & 169 \\ 
##   katsuranh4 & 0.02 & 0.00 &   7 &  49 &   4 &  12 \\ 
##   katsuranh5 & 0.05 & 0.00 &  13 & 168 &   5 &  31 \\ 
##   katsuranh6 & 0.27 & 0.00 &  22 & 528 &   6 &  70 \\ 
##   katsuranh7 & 1.82 & 0.00 &  41 & 1923 &   7 & 169 \\ 
##   noon7 & 224.42 & 0.00 & 495 & 71153 &  13 & 2892 \\ 
##    \hline
## \end{tabular}
## \caption{Experimental results for  static  using Buchberger reducer} 
## \end{table}
## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrr}
##   \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\ 
##   \hline
## butcher8 & 2.33 & 0.00 &  54 & 1796 &   4 & 2136 \\ 
##   cyclicn4 & 0.01 & 0.00 &   7 &  30 &   6 &  29 \\ 
##   cyclicn5 & 0.17 & 0.00 &  20 & 232 &   8 & 364 \\ 
##   cyclicn6 & 0.91 & 0.00 &  45 & 1135 &   9 & 1272 \\ 
##   cyclicn7 & 51.60 & 0.00 & 209 & 27185 &  12 & 11117 \\ 
##   cyclicnh4 & 0.01 & 0.00 &   7 &  30 &   6 &  29 \\ 
##   cyclicnh5 & 0.11 & 0.00 &  38 & 538 &  13 & 350 \\ 
##   cyclicnh6 & 1.01 & 0.00 &  99 & 3502 &  15 & 1344 \\ 
##   cyclicnh7 & 36.74 & 0.00 & 443 & 79897 &  19 & 8752 \\ 
##   econ4 & 0.01 & 0.00 &   7 &  29 &   2 &  35 \\ 
##   econ5 & 0.03 & 0.00 &  11 &  82 &   3 & 149 \\ 
##   econ6 & 0.09 & 0.00 &  18 & 232 &   4 & 417 \\ 
##   econ7 & 0.48 & 0.00 &  32 & 747 &   4 & 1133 \\ 
##   econh4 & 0.01 & 0.00 &   8 &  34 &   5 &  31 \\ 
##   econh5 & 0.03 & 0.00 &  15 & 104 &   7 & 142 \\ 
##   econh6 & 0.11 & 0.00 &  28 & 346 &   9 & 468 \\ 
##   econh7 & 0.43 & 0.00 &  51 & 1127 &  10 & 1185 \\ 
##   f633 & 0.84 & 0.00 &  47 & 1022 &   4 & 2098 \\ 
##   f633h & 0.56 & 0.00 &  47 & 977 &   6 & 1776 \\ 
##   fateman & 0.21 & 0.00 &  27 & 1009 &  14 & 433 \\ 
##   fatemanh & 0.25 & 0.00 &  27 & 1009 &  14 & 433 \\ 
##   katsuran4 & 0.02 & 0.00 &   7 &  49 &   4 &  44 \\ 
##   katsuran5 & 0.04 & 0.00 &  13 & 168 &   5 & 140 \\ 
##   katsuran6 & 0.16 & 0.00 &  22 & 528 &   6 & 389 \\ 
##   katsuran7 & 1.00 & 0.00 &  41 & 1923 &   7 & 1077 \\ 
##   katsuranh4 & 0.03 & 0.00 &   7 &  49 &   4 &  44 \\ 
##   katsuranh5 & 0.04 & 0.00 &  13 & 168 &   5 & 140 \\ 
##   katsuranh6 & 0.24 & 0.00 &  22 & 528 &   6 & 389 \\ 
##   katsuranh7 & 1.01 & 0.00 &  41 & 1923 &   7 & 1077 \\ 
##   noon7 & 290.10 & 0.00 & 495 & 71153 &  13 & 80906 \\ 
##    \hline
## \end{tabular}
## \caption{Experimental results for  static  using F4 reducer} 
## \end{table}
## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrr}
##   \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\ 
##   \hline
## butcher8 & 86.94 & 3.06 &  49 & 1577 &   4 & 510 \\ 
##   cyclicn4 & 0.13 & 0.08 &   7 &  30 &   6 &  12 \\ 
##   cyclicn5 & 0.54 & 0.22 &  20 & 238 &   8 & 120 \\ 
##   cyclicn6 & 7.20 & 0.77 &  44 & 1119 &  11 & 399 \\ 
##   cyclicn7 & 491.97 & 11.23 & 209 & 27185 &  12 & 2099 \\ 
##   cyclicnh4 & 0.09 & 0.05 &   7 &  30 &   6 &  12 \\ 
##   cyclicnh5 & 0.45 & 0.20 &  31 & 438 &  11 &  99 \\ 
##   cyclicnh6 & 27.68 & 1.65 &  46 & 2065 &  13 & 470 \\ 
##   cyclicnh7 & 790.06 & 17.42 & 181 & 45324 &  17 & 1476 \\ 
##   econ4 & 0.05 & 0.04 &   7 &  29 &   2 &  13 \\ 
##   econ5 & 0.12 & 0.09 &  11 &  82 &   3 &  28 \\ 
##   econ6 & 0.27 & 0.14 &  18 & 232 &   4 &  61 \\ 
##   econ7 & 0.95 & 0.15 &  32 & 747 &   4 & 153 \\ 
##   econh4 & 0.06 & 0.04 &   8 &  34 &   5 &  14 \\ 
##   econh5 & 88.86 & 3.53 &  17 & 123 &   8 & 489 \\ 
##   econh6 & 1.76 & 0.28 &  31 & 407 &   9 & 167 \\ 
##   econh7 & NA & NA & NA & NA & NA & NA \\ 
##   f633 & 5.57 & 0.48 &  41 & 1075 &   5 & 234 \\ 
##   f633h & 39.07 & 1.15 &  46 & 1047 &   6 & 346 \\ 
##   fateman & 9.30 & 0.71 &  25 & 1017 &  13 & 181 \\ 
##   fatemanh & 115.28 & 4.57 &  23 & 1049 &  13 & 491 \\ 
##   katsuran4 & 0.06 & 0.04 &   7 &  49 &   4 &  12 \\ 
##   katsuran5 & 0.17 & 0.09 &  13 & 168 &   5 &  34 \\ 
##   katsuran6 & 0.41 & 0.14 &  22 & 528 &   6 &  70 \\ 
##   katsuran7 & 2.26 & 0.36 &  41 & 1923 &   7 & 169 \\ 
##   katsuranh4 & 0.06 & 0.04 &   7 &  49 &   4 &  12 \\ 
##   katsuranh5 & 0.15 & 0.09 &  13 & 168 &   5 &  31 \\ 
##   katsuranh6 & 0.44 & 0.16 &  22 & 528 &   6 &  70 \\ 
##   katsuranh7 & 2.34 & 0.35 &  41 & 1923 &   7 & 169 \\ 
##   noon7 & NA & NA & NA & NA & NA & NA \\ 
##    \hline
## \end{tabular}
## \caption{Experimental results for  random  using Buchberger reducer} 
## \end{table}
## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrr}
##   \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\ 
##   \hline
## butcher8 & 2.80 & 0.13 &  54 & 1796 &   4 & 2481 \\ 
##   cyclicn4 & 0.01 & 0.00 &   7 &  30 &   6 &  43 \\ 
##   cyclicn5 & 0.31 & 0.10 &  20 & 237 &   8 & 604 \\ 
##   cyclicn6 & 1.53 & 0.14 &  45 & 1135 &   9 & 1710 \\ 
##   cyclicn7 & 66.48 & 1.13 & 209 & 27185 &  12 & 13791 \\ 
##   cyclicnh4 & 0.02 & 0.00 &   7 &  30 &   6 &  43 \\ 
##   cyclicnh5 & 0.31 & 0.10 &  38 & 533 &  14 & 682 \\ 
##   cyclicnh6 & 1.81 & 0.12 &  65 & 2594 &  14 & 2032 \\ 
##   cyclicnh7 & 59.97 & 0.34 & 443 & 79897 &  19 & 14430 \\ 
##   econ4 & 0.06 & 0.04 &   7 &  29 &   2 &  36 \\ 
##   econ5 & 0.09 & 0.05 &   8 &  65 &   5 & 150 \\ 
##   econ6 & 0.14 & 0.05 &  17 & 229 &   4 & 414 \\ 
##   econ7 & 0.49 & 0.05 &  32 & 747 &   4 & 1133 \\ 
##   econh4 & 0.06 & 0.05 &   7 &  33 &   5 &  36 \\ 
##   econh5 & 0.10 & 0.04 &  16 & 117 &   7 & 245 \\ 
##   econh6 & 0.23 & 0.05 &  29 & 404 &   8 & 647 \\ 
##   econh7 & 11.55 & 0.10 &  56 & 1516 &   9 & 8562 \\ 
##   f633 & 0.76 & 0.06 &  45 & 998 &   4 & 2360 \\ 
##   f633h & 0.67 & 0.06 &  47 & 990 &   6 & 2076 \\ 
##   fateman & 0.35 & 0.11 &  26 & 1004 &  14 & 514 \\ 
##   fatemanh & 0.32 & 0.10 &  27 & 1009 &  14 & 471 \\ 
##   katsuran4 & 0.06 & 0.04 &   6 &  47 &   4 &  86 \\ 
##   katsuran5 & 0.11 & 0.05 &  13 & 168 &   5 & 219 \\ 
##   katsuran6 & 0.27 & 0.05 &  22 & 528 &   6 & 537 \\ 
##   katsuran7 & 1.26 & 0.05 &  41 & 1923 &   7 & 1346 \\ 
##   katsuranh4 & 0.07 & 0.05 &   7 &  49 &   4 &  44 \\ 
##   katsuranh5 & 0.12 & 0.05 &  13 & 168 &   5 & 219 \\ 
##   katsuranh6 & 0.27 & 0.05 &  22 & 528 &   6 & 537 \\ 
##   katsuranh7 & 1.10 & 0.06 &  41 & 1923 &   7 & 1346 \\ 
##   noon7 & 352.98 & 0.45 & 495 & 71153 &  13 & 116239 \\ 
##    \hline
## \end{tabular}
## \caption{Experimental results for  random  using F4 reducer} 
## \end{table}
## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrr}
##   \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\ 
##   \hline
## butcher8 & NA & NA & NA & NA & NA & NA \\ 
##   cyclicn4 & 0.42 & 0.32 &   5 &  21 &   5 &   8 \\ 
##   cyclicn5 & 7.34 & 6.83 &  10 &  89 &  15 & 105 \\ 
##   cyclicn6 & 133.30 & 120.09 &  17 & 351 &  48 & 346 \\ 
##   cyclicn7 & NA & NA & NA & NA & NA & NA \\ 
##   cyclicnh4 & 0.34 & 0.30 &   5 &  21 &   5 &   8 \\ 
##   cyclicnh5 & 4.55 & 4.42 &  21 & 293 &  12 &  49 \\ 
##   cyclicnh6 & 41.15 & 39.59 &  48 & 1706 &  13 & 150 \\ 
##   cyclicnh7 & NA & NA & NA & NA & NA & NA \\ 
##   econ4 & 0.37 & 0.35 &   5 &  22 &   3 &  11 \\ 
##   econ5 & 0.98 & 0.93 &   6 &  48 &   6 &  15 \\ 
##   econ6 & 4.33 & 4.17 &   9 & 139 &   7 &  44 \\ 
##   econ7 & 28.14 & 27.06 &  18 & 482 &  12 & 109 \\ 
##   econh4 & 1.01 & 0.97 &   8 &  83 &   6 &  15 \\ 
##   econh5 & 6.14 & 6.01 &  14 & 358 &   7 &  35 \\ 
##   econh6 & 62.41 & 61.49 &  31 & 1799 &   8 & 110 \\ 
##   econh7 & 683.08 & 676.53 &  66 & 5589 &  10 & 306 \\ 
##   f633 & 19.57 & 18.44 &  42 & 1031 &   7 & 192 \\ 
##   f633h & 3132.36 & 3123.84 &  34 & 4677 &   8 & 141 \\ 
##   fateman & 30.59 & 29.89 &  44 & 1933 &  20 & 113 \\ 
##   fatemanh & 37.95 & 37.55 &  33 & 1321 &  16 &  81 \\ 
##   katsuran4 & 0.59 & 0.55 &   7 &  49 &   4 &  12 \\ 
##   katsuran5 & 2.88 & 2.75 &  12 & 182 &   6 &  32 \\ 
##   katsuran6 & 37.26 & 36.12 &   8 & 257 &  20 &  93 \\ 
##   katsuran7 & 48.00 & 45.06 &  44 & 2200 &   7 & 181 \\ 
##   katsuranh4 & 0.84 & 0.78 &   7 &  55 &   4 &  12 \\ 
##   katsuranh5 & 3.11 & 2.98 &  14 & 194 &   5 &  34 \\ 
##   katsuranh6 & 25.50 & 24.72 &  30 & 828 &   8 & 109 \\ 
##   katsuranh7 & NA & NA & NA & NA & NA & NA \\ 
##   noon7 & NA & NA & NA & NA & NA & NA \\ 
##    \hline
## \end{tabular}
## \caption{Experimental results for  localsearch  using Buchberger reducer} 
## \end{table}
## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrr}
##   \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\ 
##   \hline
## butcher8 & 837.40 & 823.00 &  31 & 1019 &   5 & 7019 \\ 
##   cyclicn4 & 0.41 & 0.38 &   6 &  28 &   8 &  69 \\ 
##   cyclicn5 & 11.19 & 9.63 &  11 & 102 &  15 & 3524 \\ 
##   cyclicn6 & 188.25 & 174.14 &  53 & 1347 &  13 & 9172 \\ 
##   cyclicn7 & NA & NA & NA & NA & NA & NA \\ 
##   cyclicnh4 & 0.56 & 0.53 &   7 &  27 &   8 &  64 \\ 
##   cyclicnh5 & 4.36 & 4.12 &  17 & 254 &  10 & 876 \\ 
##   cyclicnh6 & 90.99 & 86.12 &  59 & 2113 &  13 & 5903 \\ 
##   cyclicnh7 & NA & NA & NA & NA & NA & NA \\ 
##   econ4 & 0.28 & 0.25 &   7 &  29 &   2 &  74 \\ 
##   econ5 & 1.16 & 0.99 &   8 &  55 &   5 & 302 \\ 
##   econ6 & 8.00 & 7.07 &   8 & 136 &   9 & 1840 \\ 
##   econ7 & 39.67 & 37.61 &  23 & 647 &   8 & 4002 \\ 
##   econh4 & 0.65 & 0.60 &   8 &  33 &   6 & 121 \\ 
##   econh5 & 2.79 & 2.62 &  20 & 156 &  10 & 656 \\ 
##   econh6 & 12.01 & 10.96 &  36 & 527 &   9 & 2786 \\ 
##   econh7 & 40.26 & 38.68 &  47 & 1113 &   8 & 2864 \\ 
##   f633 & 13.51 & 12.08 &  32 & 679 &   7 & 3694 \\ 
##   f633h & 63.01 & 61.52 &  44 & 977 &   6 & 3996 \\ 
##   fateman & 29.34 & 27.36 &  42 & 1834 &  20 & 2761 \\ 
##   fatemanh & 30.16 & 29.37 &  29 & 1127 &  15 & 1479 \\ 
##   katsuran4 & 0.63 & 0.58 &   7 &  54 &   4 & 128 \\ 
##   katsuran5 & 2.16 & 2.03 &  13 & 170 &   5 & 413 \\ 
##   katsuran6 & 19.28 & 17.96 &  20 & 583 &   8 & 2218 \\ 
##   katsuran7 & 142.63 & 132.00 &  34 & 1938 &  10 & 8726 \\ 
##   katsuranh4 & 0.78 & 0.75 &   7 &  55 &   4 &  92 \\ 
##   katsuranh5 & 13.36 & 12.50 &  30 & 459 &  12 & 2237 \\ 
##   katsuranh6 & 11.34 & 10.56 &  23 & 586 &   6 & 1244 \\ 
##   katsuranh7 & NA & NA & NA & NA & NA & NA \\ 
##   noon7 & NA & NA & NA & NA & NA & NA \\ 
##    \hline
## \end{tabular}
## \caption{Experimental results for  localsearch  using F4 reducer} 
## \end{table}

Checking out Random results

Every instance / reducer has been run at least 2 times.

## # A tibble: 60 x 3
## # Groups:   reducer [2]
##    reducer   instance      n
##    <fct>     <fct>     <int>
##  1 classical butcher8      8
##  2 classical cyclicn4      6
##  3 classical cyclicn5     11
##  4 classical cyclicn6     12
##  5 classical cyclicn7      7
##  6 classical cyclicnh4    13
##  7 classical cyclicnh5    17
##  8 classical cyclicnh6     7
##  9 classical cyclicnh7    13
## 10 classical econ4         5
## # … with 50 more rows

#Checking out GS and GFans

## # A tibble: 7 x 3
##   instance    minG mindeg
##   <fct>      <int>  <int>
## 1 econ5          5      3
## 2 econh4         4      3
## 3 katsuranh4     7      4
## 4 katsuran4      4      4
## 5 cyclicn4       5      5
## 6 cyclicnh4      4      4
## 7 econ4          4      2
## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:41 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lrrrrrrrr}
##   \hline
## instance & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred & minG & mindeg \\ 
##   \hline
## econ5 & 115.21 & 114.90 &  10 &  70 &   3 &  33 &   5 &   3 \\ 
##   econh4 & 461.15 & 459.52 &  10 &  51 &   6 & 158 &   4 &   3 \\ 
##   katsuranh4 & 5.67 & 5.60 &   7 &  49 &   4 &  30 &   7 &   4 \\ 
##   katsuran4 & 0.85 & 0.74 &   7 &  52 &   4 &  11 &   4 &   4 \\ 
##   cyclicn4 & 0.90 & 0.87 &   5 &  21 &   5 &  11 &   5 &   5 \\ 
##   cyclicnh4 & 1.88 & 1.85 &   4 &  17 &   4 &  10 &   4 &   4 \\ 
##   econ4 & 1.10 & 1.05 &   4 &  18 &   2 &  12 &   4 &   2 \\ 
##    \hline
## \end{tabular}
## \caption{Experimental results for GS using Buchberger reducer} 
## \end{table}

Behavior in cyclics / homogeneous cyclics

## Warning: Removed 1 rows containing missing values (geom_path).

## Warning: Removed 1 rows containing missing values (geom_path).

## Warning: Removed 1 rows containing missing values (geom_path).

## Warning: Removed 1 rows containing missing values (geom_path).

## Warning: Removed 1 rows containing missing values (geom_path).

## Warning: Removed 1 rows containing missing values (geom_path).

Generating data on Gröbner fans

## Warning: Removed 1 rows containing missing values (geom_point).

## Warning: Removed 1 rows containing missing values (geom_point).

## Warning: Removed 1 rows containing missing values (geom_point).

## Warning: Removed 2 rows containing missing values (geom_point).

## Warning: Removed 1 rows containing missing values (geom_point).

## Warning: Removed 3 rows containing missing values (geom_point).

I noticed perturbation and random are measuring overhead 0 when the reducer is F4. Why? Is it a problem in the measurement or in the R code?

## Adding missing grouping variables: `instance`, `algorithm`
## # A tibble: 60 x 3
## # Groups:   instance, algorithm [60]
##    instance algorithm    dynamic
##    <fct>    <fct>          <dbl>
##  1 butcher8 perturbation  0.270 
##  2 butcher8 random        0.134 
##  3 cyclicn4 perturbation  0     
##  4 cyclicn4 random        0     
##  5 cyclicn5 perturbation  0.121 
##  6 cyclicn5 random        0.0992
##  7 cyclicn6 perturbation  0.169 
##  8 cyclicn6 random        0.139 
##  9 cyclicn7 perturbation  2.14  
## 10 cyclicn7 random        1.13  
## # … with 50 more rows

The problem is that in a few cases, the overhead is 0. Then, the geometric mean is 0. I can just drop zeroes from the gmean computation.

## % latex table generated in R 3.6.1 by xtable 1.8-4 package
## % Mon Nov 18 14:41:59 2019
## \begin{table}[ht]
## \centering
## \begin{tabular}{lllrrrrrr}
##   \hline
## instance & Algorithm & Reducer & $t$ & $O$ & $|G|$ & $|\Supp(G)|$ & $\deg$ & sred \\ 
##   \hline
## cyclicnh6 & caboara-perry & classical & 2.92 & 1.44 & 48.00 & 2580.00 & 14.00 & 153.00 \\ 
##   cyclicnh6 & caboara-perry & F4 & 8.47 & 7.49 & 43.00 & 2112.00 & 12.00 & 899.00 \\ 
##   cyclicnh6 & perturbation & classical & 1.14 & 0.51 & 34.00 & 1540.00 & 9.00 & 102.00 \\ 
##   cyclicnh6 & perturbation & F4 & 0.41 & 0.08 & 34.00 & 1540.00 & 9.00 & 515.00 \\ 
##   cyclicnh6 & static & classical & 4.91 & 0.00 & 99.00 & 3502.00 & 15.00 & 389.00 \\ 
##   cyclicnh6 & static & F4 & 1.01 & 0.00 & 99.00 & 3502.00 & 15.00 & 1344.00 \\ 
##   cyclicnh6 & random & classical & 27.68 & 1.65 & 46.83 & 2065.00 & 13.67 & 470.17 \\ 
##   cyclicnh6 & random & F4 & 1.81 & 0.12 & 65.33 & 2594.00 & 14.00 & 2032.33 \\ 
##   cyclicnh6 & localsearch & classical & 41.15 & 39.59 & 48.00 & 1706.00 & 13.00 & 150.00 \\ 
##   cyclicnh6 & localsearch & F4 & 90.99 & 86.12 & 59.00 & 2113.00 & 13.00 & 5903.00 \\ 
##   cyclicnh7 & caboara-perry & classical & 68.93 & 28.48 & 113.00 & 29371.00 & 13.00 & 429.00 \\ 
##   cyclicnh7 & caboara-perry & F4 & 146.30 & 111.59 & 160.00 & 38330.00 & 15.00 & 5999.00 \\ 
##   cyclicnh7 & perturbation & classical & 44.31 & 4.17 & 121.00 & 28595.00 & 12.00 & 467.00 \\ 
##   cyclicnh7 & perturbation & F4 & 18.35 & 0.53 & 121.00 & 28595.00 & 12.00 & 3705.00 \\ 
##   cyclicnh7 & static & classical & 488.70 & 0.00 & 443.00 & 79897.00 & 19.00 & 2199.00 \\ 
##   cyclicnh7 & static & F4 & 36.74 & 0.00 & 443.00 & 79897.00 & 19.00 & 8752.00 \\ 
##   cyclicnh7 & random & classical & 790.06 & 17.42 & 181.17 & 45324.33 & 17.33 & 1476.00 \\ 
##   cyclicnh7 & random & F4 & 59.97 & 0.34 & 443.00 & 79897.00 & 19.00 & 14430.00 \\ 
##   cyclicnh7 & localsearch & classical & NA & NA & NA & NA & NA & NA \\ 
##   cyclicnh7 & localsearch & F4 & NA & NA & NA & NA & NA & NA \\ 
##   cyclicnh8 & static & F4 & 1950.10 & 0.00 & 1182.00 & 676462.00 & 29.00 & 72296.00 \\ 
##   cyclicnh8 & perturbation & classical & 1777.19 & 68.64 & 455.00 & 415782.00 & 17.00 & 2220.00 \\ 
##   cyclicnh8 & perturbation & F4 & 1820.61 & 2.51 & 455.00 & 415782.00 & 17.00 & 50872.00 \\ 
##   cyclicnh8 & static & classical & 11114.02 & 0.00 & 1182.00 & 676462.00 & 29.00 & 7026.00 \\ 
##   cyclicnh8 & caboara-perry & classical & 16730.38 & 14118.22 & 538.00 & 486535.00 & 20.00 & 2710.00 \\ 
##   cyclicnh8 & random & classical & 6732.86 & 93.15 & 635.19 & 547311.89 & 21.59 & 3674.48 \\ 
##   cyclicnh8 & random & F4 & 6233.03 & 2.43 & 804.07 & 616809.19 & 22.96 & 109107.44 \\ 
##    \hline
## \end{tabular}
## \caption{Results for some homogeneous Cyclic ideals.} 
## \end{table}

Caboara, Massimo, and John Perry. 2014. “Reducing the size and number of linear programs in a dynamic Gröbner basis algorithm.” Applicable Algebra in Engineering, Communications and Computing 25 (1-2): 99–117. https://doi.org/10.1007/s00200-014-0216-5.

Faugère, Jean-Charles. 1999. “A new efficient algorithm for computing Gröbner bases (F4).” Journal of Pure and Applied Algebra 139 (1). Elsevier: 61–88.

Gritzmann, Peter, and Bernd Sturmfels. 1993. “Minkowski Addition of Polytopes: Computational Complexity and Application to Gröbner Bases.” SIAM J. Disc. Math. 6 (2): 246–69.

Perry, John. 2017. “Exploring the Dynamic Buchberger Algorithm.” In Proceedings of the 2017 International Symposium on Symbolic and Algebraic Computation, 365–72.